package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.List;

public class Code11_NQueens {

	public static List<List<String>> solveNQueens(int n, List<List<String>> res) {

		char[][] chess = new char[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				chess[i][j] = '.';
			}
		}

		backtrack(chess, 0, res);
		return res;
	}

	static int ways = 0;

	public static void backtrack(char[][] chess, int row, List<List<String>> res) {
		if (row == chess.length) {
			ways++;
			res.add(construct(chess));
			return;
		}

		for (int i = 0; i < chess.length; i++) {
			if (isValid(chess, row, i)) {
				chess[row][i] = 'Q';
				backtrack(chess, row + 1, res);
				chess[row][i] = '.';
			}
		}
	}

	public static boolean isValid(char[][] chess, int row, int col) {
		int n = chess.length;

		for (int i = 0; i < row; i++) {
			if (chess[i][col] == 'Q') {
				return false;
			}
		}

		for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
			if (chess[i][j] == 'Q') {
				return false;
			}
		}

		for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
			if (chess[i][j] == 'Q') {
				return false;
			}
		}

		return true;
	}

	// 把数组转为list
	private static List<String> construct(char[][] chess) {
		List<String> path = new ArrayList<>();
		for (int i = 0; i < chess.length; i++) {
			path.add(new String(chess[i]));
		}
		return path;
	}

	public static void main(String[] args) {
		List<List<String>> result = new ArrayList<>();
		result = solveNQueens(8, result);
		System.out.println(ways);
		System.out.println(result);
	}

//	输入：4
//	输出：[
//	 [".Q..",  // 解法 1
//	  "...Q",
//	  "Q...",
//	  "..Q."],
//
//	 ["..Q.",  // 解法 2
//	  "Q...",
//	  "...Q",
//	  ".Q.."]
//	]
//	解释: 4 皇后问题存在两个不同的解法。
}
